import java.util.Arrays;
// 基数排序
// 测试链接 : https://leetcode.cn/problems/sort-an-array/
public class RadixSort {

    public static int MAX = 50001;

    //标记处理多少进制的数
    public static int BASE = 10;

    //桶 记录每个位置上数的个数
    public static int[] cnts = new int[BASE];
    //辅助数组
    public static int[] help = new int[MAX];

    public static void main(String[] args) {
        int[] num = {187,235,-12,1,78};
        sortArray(num);
        for(int e : num) {
            System.out.print(e + " ");
        }
    }
    public static int[] sortArray(int[] nums) {
        int n = nums.length;
        int min = 0;
        for(int a : nums) {
            min = Math.min(min,a);
        }
        int max = 0;
        for(int i = 0; i < n; i++) {
            nums[i] -= min;
            max = Math.max(max,nums[i]);
        }
        int bits = getBits(max);
        radixSort(nums,n,bits);

        for(int i = 0; i < n; i++) {
            nums[i] += min;
        }
        return nums;
    }

    //获取一个数字的位数
    public static int getBits(int number) {
        int ans = 0;
        while (number > 0) {
            number/=10;
            ans++;
        }
        return ans;
    }

    //只能处理非负整数
    public static void radixSort(int[] num, int n, int bits) {
        for(int offset = 1; bits > 0; bits--, offset*=10) {
            //清空桶
            Arrays.fill(cnts,0);
            //记录每位上的数字存在的个数
            for (int data : num) {
                cnts[(data/offset)%BASE]++;
            }
            //计算前缀数量和
            for(int i = 1 ; i < BASE; ++i) {
                cnts[i] = cnts[i] + cnts[i-1];
            }
            for(int i = n-1 ; i >= 0; i--) {
                // 前缀数量分区的技巧
                // 数字提取某一位的技巧
                help[--cnts[(num[i]/offset)%BASE] ] = num[i];
            }
            //将排好的序覆盖给原数组
            for(int i = 0; i < n; ++i) {
                num[i] = help[i];
            }
        }
    }

}
